package org.shj.algorithm;

/**
 * 给定一个数组，给定一个值 sum，找出数组中的若干个数，使其和为 sum，找出所有组合
 * 说明：对于每一个数都有取和不取两种可能，所以时间复杂度是：2 的 N 次方
 *
 * @author Shen Huang Jian
 * @date 2019/4/16
 */
public class FindSum {

    public static void main(String[] args){
        //int[] array = {1, 2, 3, 4, 5};
        //int sum = 10;

        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int sum = 40;
        //method1(array, sum);
        method2(array, sum);
    }

    /**
     *
     * @param array
     * @param sum
     */
    private static void method1(int[] array, int sum){
        boolean[] bool = new boolean[array.length];
        find(array, sum, bool, 0, 0);
    }

    /**
     *
     * @param array 原数组
     * @param sum 要求的和
     * @param bool 对应数据中相应位置的数是否取其值用于计算 sum
     * @param i 原数组中的第几个数
     * @param has 已经加起来的和
     */
    private static void find(int[] array, int sum, boolean[] bool, int i, int has){
        if(i >= array.length){
            return;
        }
        if(has + array[i] == sum){
            bool[i] = true;
            printCombination(array, bool);
        }

        //包含第 i 个元素时的情况
        bool[i] = true;
        find(array, sum, bool, i+1, has + array[i]);

        //不包含第 i 个元素时的情况
        bool[i] = false;
        find(array, sum, bool, i+1, has);
    }

    private static void printCombination(int[] array, boolean[] bool){
        for(int i = 0; i < array.length; i++){
            if(bool[i]){
                System.out.print(array[i]);
                System.out.print(", ");
            }
        }
        System.out.println();
    }

    /**
     * 使用分枝限界法。此方法只考虑数组中都是正数的情况.
     * @param array
     * @param sum
     */
    private static void method2(int[] array, int sum){
        int remain = 0;
        for(int item : array){
            remain += item;
        }
        boolean[] bool = new boolean[array.length];
        find(bool, array, 0, sum, 0, remain);
    }

    /**
     * 对 method1 中的方法进行改进，取或不取 array[i] 进行后续计算时，
     * 添加相应的条件，以减少次数
     * @param bool
     * @param array
     * @param i
     * @param sum
     * @param has
     * @param remain
     */
    private static void find(boolean[] bool, int[] array, int i, int sum, int has, int remain){
        if(i >= bool.length){
            return;
        }

        if(has + array[i] == sum){
            bool[i] = true;
            printCombination(array, bool);

        }else if (has + array[i] < sum && has + remain >= sum){
            bool[i] = true;
            find(bool, array, i+1, sum, has + array[i], remain - array[i]);
        }

        if(has + remain - array[i] >= sum){
            bool[i] = false;
            find(bool, array, i+1, sum, has, remain - array[i]);
        }
    }
}
